Graph Traversal: Breadth-First Search (BFS)

Algorithm: Breadth-First Search (BFS)

BFS is a fundamental graph traversal algorithm used to explore a graph $G=(V, E)$ systematically, finding the shortest path (in terms of edges) from a source node $s$ to all other reachable nodes. It guarantees nodes are processed in increasing order of distance.

BFS Mechanism

1. Initialization: For every node $v$, set `color` to `WHITE` (unvisited), distance $d[v] = \infty$, and parent $\pi[v] = \text{NIL}$.
2. Source Setup: Set the source $s$ to `GRAY` (discovered), $d[s]=0$, and initialize a FIFO Queue $Q$ with $s$.
3. Exploration Loop: While $Q$ is not empty, dequeue node $u$:
   • For every neighbor $v$ of $u$:
     • If $v$ is `WHITE`:
       • Set $v$ to `GRAY`.
       • $d[v] = d[u] + 1$ (Level increment).
       • $\pi[v] = u$ (Record parent).
       • Enqueue $v$.
   • Once all neighbors are processed, mark $u$ as `BLACK` (fully explored).

Key BFS Properties & Use Cases

The Power of the Queue: BFS fundamentally relies on the FIFO property of the Queue. This ensures that the algorithm visits all nodes at distance $k$ from the source before visiting any nodes at distance $k+1$. This level-by-level exploration guarantees unweighted shortest paths.

Connectivity and Levels:

1. Levels: The value $d[v]$ represents the minimum number of edges needed to reach $v$ from $s$. This is the shortest path length.
2. BFS Tree: The set of parent pointers $\pi$ implicitly defines the BFS Tree, which is a subgraph containing only shortest-path edges from $s$.
3. Use Cases: Finding shortest paths (unweighted), networking broadcast, web crawlers (finding minimum link depth), and garbage collection (reachable objects).

BFS Complexity Analysis

BFS is highly efficient, examining every vertex and edge exactly once, provided the graph is represented using an Adjacency List.

Metric	Cost (Adjacency List)	Explanation
Initialization	$O(|V|)$	Processing all $n$ vertices once.
Queue Operations	$O(|V|)$	Each vertex is enqueued and dequeued exactly once.
Edge Examination	$O(|E|)$	The total time spent scanning adjacency lists is proportional to the number of edges $m$.
Total Runtime	$O(|V| + |E|) = O(n+m)$	Linear time complexity relative to the size of the graph.